//打家劫舍
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        vector<int> g(n + 1);
        for (int i = 1; i <= n; i++) {
            f[i] = max(f[i - 1], g[i - 1] + nums[i - 1]);
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n], g[n]);
    }
};

//单词拆分
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        int m = wordDict.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                if (wordDict[j].size() > i)
                    continue;
                else {
                    int t = wordDict[j].size();
                    // cout<<t;
                    if (s.substr(i - t, t) == wordDict[j]) {
                        //cout << t;

                        if (dp[i - t]) {
                            dp[i] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[n];
    }
};